package com.mlh.skill;

/**
 * @author 缪林辉
 * @date 2024/7/2 14:50
 * @DESCRIPTION
 */
//给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
// 我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
// 必须在不使用库内置的 sort 函数的情况下解决这个问题。
public class 颜色分类 {
    //用可以原地的排序算法就可以完成
    //冒泡  选择  插入  希尔  堆排序  快速
    //这题就是荷兰国旗问题
    public void method1(int[] nums) {
        int left=-1,right=nums.length;
        int index=0;
        while(index<right) {
            if(nums[index]<1){
                int temp=nums[++left];
                nums[left]=nums[index];
                nums[index]=temp;
                index++;
            }else if(nums[index]>1){
                int temp=nums[--right];
                nums[right]=nums[index];
                nums[index]=temp;
            }else {
                index++;
            }
        }
    }

    //nums[index]=nums[index]^nums[right];
    //nums[right]=nums[index]^nums[right];
    //nums[index]=nums[index]^nums[right];
    // 如果index 和right是同一个下标
    //那么在用异或的方式就会出现错误
    // 比如nums[index]=2   index和right相同
    // 在第一个代码执行后，nums[index]=0  连带着nums[right]也为0
    public static void practice(int[] nums){
        int left=-1,right=nums.length;
        int index=0;
        while(index<right){
            if(nums[index]>1){
                int temp=nums[index];
                --right;
                nums[index]=nums[right];
                nums[right]=temp;
            }else if(nums[index]<1){
                int temp=nums[index];
                ++left;
                nums[index]=nums[left];
                nums[left]=temp;
                ++index;
            }else{
                ++index;
            }
        }
    }
}
